1. Field of the Invention
The present invention relates to a method and a device for transmitting a sequence of messages in a point-to-point interconnection network.
2. Description of the Relevant Art
Interconnection networks are means of transmitting messages between different electronic or data processing agents, or communicating entities. A transmission can be carried out without processing the message or with processing the message. The expression “message transmission” is used in all cases. The expression “processing a message” is understood to be, for example, an analysis of data contained in the message or an addition of data to the message.
A message is, of course, a series of information technology data, that is to say a series of bits or bytes arranged with specific semantics and representing a complete item of atomic information. Each message comprises a message header, which principally comprises the destination address of the message and the size of the message.
These interconnection networks are generally composed of two separate parts which interact, namely a hardware part comprising physical links and a hard-wired or micro-programmed network controller, which executes a low level protocol, and a software part for forming an interface with software functions of higher level.
An ideal interconnection network would certainly be a totally interconnected network, that is to say a network in which each pair of agents is connected by a point-to-point link. This is unrealistic however as it becomes too complicated as soon as there are more than a few dozen agents. It is therefore desirable that the interconnection network can provide all of the communications between agents with a limited number of links per agent.
There are specialized agents for performing a routing or switching or transmission of the messages circulating in the interconnection network.
In a point-to-point interconnection network, an agent's input is connected to at most one message initiating agent, or to at most one message transmission agent.
Interconnection networks comprise transmission devices or routers (or “switches”), an organization of the network providing the link between the routers and the other agents and a routing assembly which provides the circulation of messages within the organization of the network.
A router is an active agent of the interconnection network which receives on input messages coming from one or more agents and which directs or routes each of these messages to its destination agent or to another router respectively. This routing is carried out by means of the address of the destination agent of the message, or target agent, which is present in the header of the message to be routed.
The organization of a network constitutes the physical structure connecting the various nodes or connection points of an interconnection network.
The routing assembly manages the way in which a message is routed or directed from a source agent transmitting the message to a destination agent of the message through routers by following a routing path.
Any agent present in an interconnection network can transmit and/or receive messages. The routing technique determines the way in which the messages are transmitted from the transmission agent, which creates the message, to the destination agent or target agent. For a given interconnection network, there are different routing techniques, for which the objectives are to reduce the end of message latency, or end of message routing delay, of a message from the transmission agent to the destination agent, to increase the overall throughput and to improve the overall reliability of the network. The latency includes all of the waiting times due to the way in which the messages propagate in the network and, more particularly, through the message transmission devices whose task is to route the messages. The throughput is the quantity of computer data that a link of the network can convey per unit time, and can be measured locally on a link of the interconnection network or globally over the whole of the interconnection network. The reliability of a network is important, since the probability of errors grows rapidly with the number of nodes in an interconnection network.
A transmission agent comprises at least one input comprising a storage means organized as queue of messages of the “First In First Out” (FIFO) type and at least one output comprising a message transmission means capable of deciding which message to transmit. Only the first messages of the input queues are visible to the transmission agent.
Many software applications necessitate the accessing of identical data. For example, it is not necessary, when an application modifies an item of data and when another application or the same application necessitates accessing the modified value of that item of data, for it to access it before the end of its modification. Solutions have been developed to ensure this and they are generally based on the concept of a set of atomic actions, or a set of indivisible actions, in other words on a series of actions that cannot be interrupted by other actions.
An atomic transaction of the read-modify-write type is an indivisible sequence consisting of a step of reading data at a particular address of a target agent, followed by a step of actions modifying the data and then by a writing at the initial address of the new values of the modified data. These special transactions prohibit modifications in parallel of the same item of data. It is the hardware part of the system which directly manages these types of transactions. Current atomic transactions of this type are generally increments, decrements, initializations or deletions.
There are also transactions carried out on locked data busses and based on the use of a bus locking signal. This locking signal acts directly on the transmission or switching or decision means of the data bus in such a way that as long as the locking signal is valid, only the transmission agent of that locking message can transmit messages on the data bus and act on data, which guarantees the atomicity of the processing in progress. When the bus is locked, only messages arriving at the input connected to the initiating agent can be transmitted on the output allowing the messages to be transmitted to the destination agent.
In an interconnection network, it is not possible to guarantee, by construction, the atomicity of a complete transaction since a transmission agent can interlace messages coming from several initiating agents and destined for a same destination agent, thus breaking the atomicity of the first transaction in the process of switching or transmission or routing.
In the light of the above, it is also an objective of the invention to guarantee the atomicity of an original sequence of messages from a transmission agent destined for a target agent. In other words, it is a matter of transmitting an indivisible sequence of messages, from an initiating agent to a destination agent, whilst locking only one output onto an input for the transmission agents located in the path of the messages of the indivisible sequence.